Topic: Computability - space and time constraints

February 18, 2016

Computability

    Almost all of the computers in existence can only do simple arithmetic, logic, and some straightforward high school math operations.
    Computers work only with numbers, although the numbers can easily represent a lot of useful data, such as text, pictures, and sound.
    Some problems, such as speech recognition, require very sophisticated logic and programming and are very hard to program.
    Some activities, such as art and philosophy, are simply beyond the capabilities of any current type of computer, because they
    are not reducible to numbers and logic. Even IBM's "Watson" is primarily a data collator and processor. It is not significantly creative.

In actual practice, the limits on what a computer can do are mostly space and time.

Space

    The space constraint is determined by how much memory the computer has available.
    The memory size is the "4 Gigabytes" or "8 Gigabytes" specification you hear about when you shop for a computer.
    Memory size was very important in the early days of computers because it was so expensive,
        but now memory is so cheap that availability of enough memory is rarely a problem.

    Visual Basic Space Program, as demonstrated in class (the most important part):

    Dim limit As Integer = 1000000

    System.Console.Out.Writeline("Start of Program")

    While index < limit
        array(index) = index
        index = index + 1
    End While

    System.Console.Out.Writeline("End of Program")

Speed

    The speed of processing is now, and for the foreseeable future, the most significant restraint on computing.
    Certain problems that are easy to program can never be actually computed.
    For example, calculating all possible chess games would take the fastest computer in existence until the end
        of the Universe to complete, even though a second year computer science student could write the program.

    Visual Basic Speed Program, as demonstrated in class (the most important part):

    Dim limit As Integer = 1000000

    System.Console.Out.Writeline("Start of Program")

    While index < limit

        count = 0

        while count < 1000000
            count = count + 1
        End While

        index = index + 1

    End While

    System.Console.Out.Writeline("End of Program")